package com.fr.lintcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class Q471 {

    /**
     * @param words: an array of string
     * @param k: An integer
     * @return: an array of string
     */
    public String[] topKFrequentWords(String[] words, int k) {
        // write your code here
    	String [] rs = new String[k];
    	if(words == null) {
    		return rs;
    	}
    	Map<String, Integer> map = new HashMap<>();
    	for(String word : words) {
    		Integer i = map.get(word);
    		if(i == null) {
    			i = 0;
    		}
    		i ++;
    		map.put(word, i);
    	}
    	List<Map.Entry<String, Integer>> list = new ArrayList<>(map.entrySet());
    	Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {

			@Override
			public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
				if(!o1.getValue().equals(o2.getValue())) {
					return o2.getValue() - o1.getValue();
				}else {
					return o1.getKey().compareTo(o2.getKey());
				}
			}
		});
    	for(int i = 0; i< k; i++) {
    		rs[i] = list.get(i).getKey();
    	}
    	return rs;
    }

}
